package com.zklh.leetcode.tree.easy;

import com.zklh.leetcode.tree.model.TreeNode;

/**
 * @author 坐看落花
 * @version 1.0
 * @date 2021/5/20 22:08
 */
public class TreeNodeDeleter {

    public void delete(TreeNode root, int val) {
        delete(null, root, 0, val);
    }

    public TreeNode delete(TreeNode pre, TreeNode root,int direction, int val) {

        if (root == null) {
            return null;
        }
        TreeNode newRoot = root;
        if (root.val == val) {
            // 左子树空的
            if (root.left == null) {
                newRoot = root.right;
            } else if (root.right == null) {
                newRoot =root.left;
            } else {
                newRoot = root.left;
                append(root.left, root.right);
            }
            // 右子树是空的

            // 左右子树都不空
        } else {
            if (val < root.val) {
                delete(root, root.left, -1,val);
            } else {
                delete(root,root.right,1,val);
            }
        }

        if (pre != null) {
            if (direction == -1) {
                pre.left = newRoot;
            } else {
                pre.right = newRoot;
            }
        }
        return newRoot;

    }

    /**
     * 将节点放到最右边
     * @param root
     * @param appendedNode
     */
    private void append(TreeNode root, TreeNode appendedNode) {

        TreeNode rightest = root;

        while (rightest.right != null) {
            rightest = rightest.right;
        }
        rightest.right = appendedNode;
    }


    public static void main(String[] args) {

        TreeNode root = new TreeNode(1);
        root.right = new TreeNode(2);
        TreeNodeDeleter deleter = new TreeNodeDeleter();
        deleter.delete(root, 3);
    }
}
